package 华为OD机试B卷复用题.进阶题;

import utils.MyUtil;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Scanner;

public class HJ38_计算疫情扩散时间 {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试B卷复用题/进阶题/input/38.txt"));
        MyUtil.START();
        Solution(in);
        MyUtil.END();
    }

    // 广度优先搜索
    static void Solution(Scanner in) {
        // 初始化，把 1 的位置存到队列中
        String[] sArray = in.nextLine().split(",");
        int N = (int) Math.sqrt(sArray.length);
        int[][] matrix = new int[N][N];
        LinkedList<Integer[]> queue = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                matrix[i][j] = Integer.parseInt(sArray[i * N + j]);
                if (matrix[i][j] == 1) {
                    queue.add(new Integer[] {i, j});
                }
            }
        }
        // 处理
        // 如果全为 1 或 0，直接返回 -1。
        if (queue.size() == 0 || queue.size() == sArray.length) {
            System.out.println(-1);
            return;
        }
        int day = 0, healthy = sArray.length - queue.size();
        int[][] offset = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!queue.isEmpty() && healthy > 0) {
            Integer[] now = queue.pollFirst();
            int x = now[0];
            int y = now[1];
            day = matrix[x][y] + 1;
            healthy--;

            for (int[] direction : offset) {
                int targetX = x + direction[0];
                int targetY = y + direction[1];
                if (targetX < 0 || targetX >= N || targetY < 0 || targetY >= N) {
                    continue;
                }
                matrix[targetX][targetY] = day;
                queue.addLast(new Integer[] {targetX, targetY});
            }
        }
        System.out.println(day - 1);
    }
}
